This continuation-in-part application claims the benefit of U.S. Application Ser. No. 08/879,041 filed on Jun. 19, 1998, for the subject matter that both contained in this application and 09/879,041.
1. Field of Invention
This invention relates to a coding method, including a decoding method, for transmitting and storing the content of plain-text in the form of digital information while securing the secrecy thereof. More particularly, the invention relates to a chain coding method, wherein a Latin square, which is a conversion table, is used as a cipher key for coding and decoding, and a plain-text signal, which is used as a data to be input, consisting of a predetermined number of bits (even 1 bit will do), is used as a unit block for feedback and feedforward decoding.
2. Description of Related Art
There have been various proposed coding methods used as the means for securing secrecy of data. The typical examples of such methods are DES (Data Encryption Standard) of the United States and FEAL-8 developed by NTT (Nippon Telegraph and Telephone Corporation).
These methods use a kind of block cipher that codes or decodes input data by block unit under the control of a secret coding key and obtains secrecy-secured code (cipher) by repeating conversion.
However, such methods have a shortcoming that, as long as the same key is used, the same coding block (hereinafter referred to simply as a coded signal) is obtained from the same plain-text block (hereinafter referred to as a plain-text signal).
Such a shortcoming does not immediately allow easy analysis of code; however, when many of the same coded signals are used for coding a large amount of input data, this shortcoming may suggest some hint how to analyze such code.
For overcoming such a shortcoming, a feedback coding method as shown in FIG. 10 has been adopted. In this feedback coding method, in the coding stage A, in generating a coded signal Ci from a plain-text signal Pi (block No. i=1, 2, . . . ) using a key, a preceding coded signal Cixe2x88x921 is used as a feedback signal Cb. This feedback signal Cb and the plain-text signal Pi are combined to form the coded signal Ci. In the decoding stage B, a plain-text signal Pi is produced from the coded signal Ci using the same key, a preceding coded signal Cixe2x88x921 is used as a feedforward signal C1 and this feedforward signal Cf and coded signal Ci are combined to produce the plain-text signal Pi by decoding.
IV is an initial value signal used for coding and decoding initial plain-text signal Pi and decoding the coded signal Ci. For IV, a predetermined value is used (the value of the initial value signal IV should be assigned in advance for both the coding stage A side and decoding stage B side or assigned together with plain-text signal Pi).
Given below are the numerical expressions of the above processes.
In the above numerical expressions, a coding function f represents a predetermined coding algorithm such as DES and FEAL-8, and function g represents a specific discrete function defined for all the coded signals Ci. For example, when the simplest identity function is chosen, Vi=Cixe2x88x921, the operation xe2x80x9cxorxe2x80x9d, performed by arithmetic unit 5, combines a plain-text signal Pi and a feedback signal Cb for the purpose of coding or combines coding signal Ci and feedforward signal Cf for the purpose of decoding. This xe2x80x9cxorxe2x80x9d operation is the operation for xe2x80x9cexclusive orxe2x80x9d (addition by modulo 2) and is also a mathematically reversible operation.
Further simplifying the above numerical expressions, we obtain
To code the 1st data block, the xe2x80x9cxorxe2x80x9d operation is performed on the plain-text signal Pi (binary number of 1 digit) and the initial value signal IV (binary number of 1 digit) to obtain coded signal Ci. To code the 2nd and subsequent data blocks, the xe2x80x9cxorxe2x80x9d operation is performed on the plain-text signal Pi and the preceding coded signal Cixe2x88x921 (binary number of 1 digit), which is the feedback signal Cb, to obtain coded signal Ci.
Further, to decode the 1st data block, the xe2x80x9cxorxe2x80x9d operation is performed on the coded signal C1 with the initial value signal IV given as a feedforward value, to obtain decoded plain-text signal Pi.
For decoding the 2nd and subsequent data blocks, the xe2x80x9cxorxe2x80x9d operation is performed on the coded signal C1 with the preceding signal Cixe2x88x921 given as a feedforward signal Cf to obtain decoded plain-text signal P1.
As described above, according to the prior art, the xe2x80x9cxorxe2x80x9d operation always ends in a fixed value, that is, when the xe2x80x9cexclusive orxe2x80x9d (addition by modulo 2) operation is applied to the plain-text signal Pi and the input value of preceding coded signal C1-1 or applied to the input values of the coded signal Ci and preceding signal Cixe2x88x921.
However, according to the prior art described above, when the xe2x80x9cxorxe2x80x9d operation, that is, the xe2x80x9cexclusive orxe2x80x9d operation (addition by modulo 2) for coding/decoding by feedback coding method is performed, the result of the operation for the input value and the feedback value always ends in fixed values due to the addition by modulo 2. In other words, for the input value data blocks (binary number of 1 digit), feedback value data blocks and output value data blocks, the output value is 0 when both the input value and the feedback value is 0 or 1, while the output value is 1 when the input value and the feedback value are 0 and 1, or 1 and 0. Therefore, the result of the output is fixed for each bit, thereby causing a problem that such a system may provide some hint for data decoding.
Thus, this invention is devised to solve such a problem of the prior art by accomplishing a technical task, that is, to freely vary the values resulting from the xe2x80x9cxorxe2x80x9d operation for coding/decoding by the feedback coding method or to freely vary the values resulting from the xe2x80x9cexclusive orxe2x80x9d operation (addition by modulo 2), thereby making it extremely difficult to decode the coded input data.
In the following explanation, natural numbers are used as the elements of the matrix of a Latin square, but the Latin alphabet may also be used.
To accomplish the aforesaid technical task, an illustrative embodiment of the invention includes a coding method and a feedback coding method. The coding method provides a secrecy security system designed for transmitting and storing the content of plain-text converted into digital information while securing the secrecy of the content thereof. The feedback coding method codes using a plain-text signal having a predetermined number of bits as a unit block. An illustrative embodiment of the invention also uses a coding Latin square as a conversion table for a converter in conversion stage of the feedback coding method, uses the plain-text signal and the initial value signal for the initial conversion, and uses a plain-text signal and coded signal converted from a preceding plain-text signal as a feedback signal to specify positions of the rows and columns of the coding Latin square and to use the value of the specified position as coded signal. A feedforward decoding method for decoding by unit block of coded signal may be used. Additionally, a decoding Latin square is used as a conversion table, when the decoding Latin square corresponds to the coding Latin square for the converter in the decoding stage of the feedforward decoding method. An illustrative embodiment of the invention also uses a coded signal and the same initial value signal as is used for coding in the first conversion, and uses as feedforward signal, a coded signal and preceding coded signal for the second and subsequent conversions to use, as a decoded plain-text signal, the value obtained from decoding Latin square.
Additionally, an illustrative embodiment of the invention can include a means, whereby a converter component of decoder is formed with a decoding Latin square for performing inverse conversion to the conversion by coding Latin square, and the decoded plain-text signal is formed according to a value of the decoding Latin square determined by the value of the row or column represented by a coded signal and the value of the row or column represented by a feedforward signal, which is an initial value signal or preceding coded signal.
Also, an illustrative embodiment of the invention can include a means, whereby the converter component of the decoder is formed with the decoding Latin square corresponding to the coding Latin square, and a decoded plain-text signal is formed according to the value of the row or column represented by the coded signal and the value of the row and column of the decoding Latin square determined from the value of the initial value signal or the value of decoding Latin square represented by a feedforward signal, which is preceding coded signal.
An illustrative embodiment of the invention can include an additional means, whereby the initial value signal and the preceding coded signal input to the converter are coded by a coding function, which is a predetermined coding algorithm, and input to the coding Latin square and the decoding Latin square.
An illustrative embodiment of the invention can include another additional means, whereby, in the converter of the coding stage, the output from the coding Latin square is converted into a coded signal by a coding function, which is a predetermined coding algorithm, and in the converter of decoding stage, the input coded signal is decoded by a decoding function for conversion, which inverses the conversion performed by the coding function and input to the decoding Latin square.
An illustrative embodiment of the invention can include a means, whereby the coding Latin square and decoding Latin square respectively comprise a plurality of Latin squares, and a plurality of Latin squares are used selectively according to a predetermined sequence by being synchronized with input of the plain-text signal or input of the coded signal.
Additionally, an illustrative embodiment of the invention can include a means, whereby a plurality of coders and a plurality of decoders are connected in series respectively.
An illustrative embodiment of the invention can include a means, whereby a plurality of coders and a plurality of decoders are connected in parallel respectively; a plurality of plain-text signals are distributed according to a predetermined arrangement to be input substantially simultaneously to each of the coders, and individual plain-text signals are output substantially simultaneously from the decoders respectively and are arranged according to a predetermined sequence to be output.
An illustrative embodiment of the invention can include another additional means in the coder, whereby a preceding coded signal that precedes a given output signal is used as a feedback signal. Additionally, the illustrative embodiment can include another additional means in the decoder, whereby a preceding coded signal to a given input signal is used as feedforward signal.
An illustrative embodiment of the invention can include another additional means, whereby a preceding coded signal received from another coder is used as a feedback signal, and a preceding coded signal sent to another decoder is used as a feedforward signal.
An illustrative embodiment of the invention may also include a means, whereby a plurality of series circuits composed of a plurality of coders and a plurality of decoders, which are connected in series are provided, and a plurality of input plain-text signals are distributed among a plurality of series circuits of coders substantially simultaneously, according to a predetermined sequence, and a plurality of plain-text signals are substantially simultaneously output from the plurality of series circuits of decoders arranged according to a predetermined sequence to be output.
An illustrative embodiment of the invention can include another additional means, whereby, in each of coders connected in series, a preceding coded signal that precedes a given output signal is used as a feedback signal, and, in each of decoders connected in series, a preceding coded signal that precedes a given input coded signal is used as a feedforward signal.
An illustrative embodiment of the invention can include another additional means, whereby, in each of coders connected in series, a preceding coded signal received from a corresponding coder of the series circuit composed of other coders is used as a feedback signal, and, in decoders connected in series, a preceding coded signal received from a corresponding decoder in the series circuit of other decoders is used as a feedforward signal.
An illustrative embodiment of the invention can include a means, whereby the input of the initial value signal to the converter is made using the previously provided input line for the feedback signal or the feedforward signal of the initial value signal.
An illustrative embodiment of the invention can include a means, whereby the input of the initial value code to converter is made accompanying the initial plain-text signal or the initial coded signal.
The invention described in claim 1 can be expressed as follows
(Refer to FIG. 1):
For coding: C1=LM (Pi, Cixe2x88x921)
For decoding: Pi=LMxe2x88x921(Ci, Cixe2x88x921)
where: Pi=Plain-text signal (Signal No. i=1, 2, . . . );
Ci=Coded signal (Signal No. i=0, 1, 2, . . . );
Note, however, that, for C0=IV, the value previously used as an initial value is used; L is a Latin square used for conversion; and M is a number of a conversion table for selecting one conversion table as a key from among a plurality of Latin squares.
The value of the plain-text signal Pi and the value of the preceding coded signal Cixe2x88x921 are the values (pointers) respectively representing the positions of the rows and columns of the coding Latin square LM, while the coded signal Ci is the value of the element of the decoding Latin square LMxe2x88x921 represented by the row pointer and column pointer. Where the decoding Latin square LMxe2x88x921 is considered to be a Latin square of an inverse function as to the row or column of coding Latin square LM, when the coded signal Ci is treated as a row pointer, the coding Latin square LM is an inverse function with respect to the row. Also, where decoding Latin square LMxe2x88x921 is the same Latin square used as the coding Latin square LM, the former is a Latin square of inverse function for determining the pointer value of the row or column from the value of the element of the coding Latin square LM.
When the plain-text signal Pi and the preceding coded signal Cixe2x88x921 are input to the coding Latin square LM, the coded signal Ci is obtained as an output. When the coded signal C1 and the preceding coded signal Ci are input to the decoding Latin square LMxe2x88x921 of inverse function, a plain text signal Pi is obtained. Coding can be expressed as a value of the conversion table Ci=LM (the value of row pointer=P1, value of column pointer=Cixe2x88x921).
For decoding according to one illustrative embodiment of the invention, the value of the conversion table can be expressed as Pi=LMxe2x88x921 (value of row pointer=Ci, value of column pointer=Cixe2x88x921).
According another illustrative embodiment of the invention, the value of the row pointer can be expressed as value of row pointer Pi=LMxe2x88x921 (value of conversion table=Ci, value of column pointer=Cixe2x88x921).
The Latin square is composed of n2 number in total of numeric values arranged in a rectangular form consisting of n number of rows and n number of columns. Each of the numeric values is taken n number of times from a set of n number of numeric values (0 through nxe2x88x921) so that each of the n number of numeric values occurs once in each row and each column. Therefore, when the number of numeric values of irreducible form (standard form), which is a permutation of given reference, is given as Ln for both the first row and first column, and when n=1 through 9, the numbers of standard form are sequentially 1, 1, 1, 4, 56, 9408, 16942080, 535281401856, 377597570964258816 (total number of n-th degree is n !xc2x7(nxe2x88x921)!xc2x7(Ln), which is the available number of Latin squares for each order of number (refer to p. 1250, Mathematics Dictionary, 3rd Edition, Iwanami Shoten).
An example of degree n=4, that is, a 4th-degree Latin square of 4 rows and 4 columns and an example of a Latin square for inverse conversion of the 4th-degree Latin square are shown in FIG. 2(a) and FIG. 2(b), respectively. Here, the Latin square of FIG. 2(a) and the Latin square of FIG. 2(b) are illustrated as matrix I and matrix II, respectively.
aij (i=1 to 4; j=1 through 4) and bij (i=1 to 4; j=1 through 4) are elements of the matrices I and II respectively. i and j represent the positions of row and column respectively.
Using the Latin square for conversion into code, the conversion can be made non-linearly by performing conversion by a unit consisting of a plurality of bits. The conversion can be performed accurately and easily, since one of the value of row, value of column and value of element are determined when any two of these values are determined.
The Latin square conversion can involve conversion by a known coding function and decoding function thereby adding to the complexity and resulting difficulty of analysis.
Optionally, the preceding and subsequent coded signals can be coded based on entirely different Latin squares, so that it is substantially impossible to identify the Latin square as the key to coding from among coded signals.
Additionally, the sequence of transmission of the coded signals is not necessarily in accordance with the sequence of the contents of the coded signals, thereby making it impossible to analyze the coded signal with reference to the relationship between preceding signals and subsequent signals.
The coding can also be performed as multiplex coding thereby making it difficult to analyze coded signal.
Although coding can be performed very simply as a whole, it is also possible to provide a means for adding to the complexity of the interrelation among individual coded signals.
An initial value signal can be set and input using a dedicated circuit protected from monitoring, so that a high secrecy-security ability for initial value signal can be assured.
Additionally, in various embodiments of the present invention secrecy-security ability may be provided without the use of a dedicated circuit for input of an initial value signal and the initial value signal setting operation on the side of decoding stage.